package org.example.basic_sort;

import java.util.PriorityQueue;

/**
 * 堆排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 *
 */
public class Code09_HeapSort {



    public static void heapSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

//        //形成大根堆
//        for (int i = 0; i < arr.length; i++) {
//            heapInsert(arr,i);
//        }
        for (int i = arr.length-1; i >= 0 ; i--) {
            heapify(arr,i,arr.length);
        }

        int heapSize = arr.length;
        //交换堆顶元素与最后一个元素，然后将堆的大小减一，周而复始，变为有序
        swap(arr,0,--heapSize);
        while(heapSize > 0) {

            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }

    }


    /**
     * 向上调整
     * @param arr
     * @param index
     */
    public static void heapInsert(int[] arr,int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }

    }

    /**
     * 向下调整
     * @param arr
     * @param index
     * @param heapSize
     */
    public static void heapify(int[] arr,int index,int heapSize) {
        int left = index * 2 +1;
        while(left < heapSize) {
            //找出左右子节点中较大的
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;

            //如果父节点大于较大的子节点，则交换
            largest = arr[largest] > arr[index] ? largest : index;
            if(largest == index) {
                break;
            }

            swap(arr, index, largest);
            index = largest;
            left = index * 2 + 1;
        }

    }
    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
        heapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>();
    }

}
